
<!DOCTYPE html>

<html>
  
<!-- Mirrored from docs.sympy.org/latest/modules/utilities/enumerative.html by HTTrack Website Copier/3.x [XR&CO'2014], Sat, 15 Jan 2022 03:28:12 GMT -->
<!-- Added by HTTrack --><meta http-equiv="content-type" content="text/html;charset=utf-8" /><!-- /Added by HTTrack -->
<head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="generator" content="Docutils 0.17.1: http://docutils.sourceforge.net/" />

    <title>Enumerative &#8212; SymPy 1.9 documentation</title>
    <link rel="stylesheet" type="text/css" href="../../_static/pygments.css" />
    <link rel="stylesheet" type="text/css" href="../../_static/default.css" />
    <link rel="stylesheet" type="text/css" href="../../_static/graphviz.css" />
    <link rel="stylesheet" type="text/css" href="../../_static/plot_directive.css" />
    <link rel="stylesheet" type="text/css" href="../../../../live.sympy.org/static/live-core.css" />
    <link rel="stylesheet" type="text/css" href="../../../../live.sympy.org/static/live-autocomplete.css" />
    <link rel="stylesheet" type="text/css" href="../../../../live.sympy.org/static/live-sphinx.css" />
    
    <script data-url_root="../../" id="documentation_options" src="../../_static/documentation_options.js"></script>
    <script src="../../_static/jquery.js"></script>
    <script src="../../_static/underscore.js"></script>
    <script src="../../_static/doctools.js"></script>
    <script src="../../../../live.sympy.org/static/utilities.js"></script>
    <script src="../../../../live.sympy.org/static/external/classy.js"></script>
    <script src="../../../../live.sympy.org/static/live-core.js"></script>
    <script src="../../../../live.sympy.org/static/live-autocomplete.js"></script>
    <script src="../../../../live.sympy.org/static/live-sphinx.js"></script>
    
    <link rel="shortcut icon" href="../../_static/sympy-notailtext-favicon.ico"/>
    <link href="enumerative.html" rel="canonical" />
    
    <link rel="index" title="Index" href="../../genindex.html" />
    <link rel="search" title="Search" href="../../search.html" />
    <link rel="next" title="Iterables" href="iterables.html" />
    <link rel="prev" title="Decorator" href="decorator.html" /> 
  </head><body>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../../genindex.html" title="General Index"
             accesskey="I">index</a></li>
        <li class="right" >
          <a href="../../py-modindex.html" title="Python Module Index"
             >modules</a> |</li>
        <li class="right" >
          <a href="iterables.html" title="Iterables"
             accesskey="N">next</a> |</li>
        <li class="right" >
          <a href="decorator.html" title="Decorator"
             accesskey="P">previous</a> |</li>
        <li class="nav-item nav-item-0"><a href="../../index.html">SymPy 1.9 documentation</a> &#187;</li>
          <li class="nav-item nav-item-1"><a href="../index.html" >SymPy Modules Reference</a> &#187;</li>
          <li class="nav-item nav-item-2"><a href="index.html" accesskey="U">Utilities</a> &#187;</li>
        <li class="nav-item nav-item-this"><a href="#">Enumerative</a></li> 
      </ul>
    </div>  

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body" role="main">
            
  <section id="module-sympy.utilities.enumerative">
<span id="enumerative"></span><h1>Enumerative<a class="headerlink" href="#module-sympy.utilities.enumerative" title="Permalink to this headline">¶</a></h1>
<p>This module includes functions and classes for enumerating and
counting multiset partitions.</p>
<dl class="py function">
<dt class="sig sig-object py" id="sympy.utilities.enumerative.multiset_partitions_taocp">
<span class="sig-prename descclassname"><span class="pre">sympy.utilities.enumerative.</span></span><span class="sig-name descname"><span class="pre">multiset_partitions_taocp</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">multiplicities</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/utilities/enumerative.py#L146-L296"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.utilities.enumerative.multiset_partitions_taocp" title="Permalink to this definition">¶</a></dt>
<dd><p>Enumerates partitions of a multiset.</p>
<dl class="field-list">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><p><strong>multiplicities</strong></p>
<blockquote>
<div><p>list of integer multiplicities of the components of the multiset.</p>
</div></blockquote>
</dd>
<dt class="field-even">Yields</dt>
<dd class="field-even"><p>state</p>
<blockquote>
<div><p>Internal data structure which encodes a particular partition.
This output is then usually processed by a visitor function
which combines the information from this data structure with
the components themselves to produce an actual partition.</p>
<p>Unless they wish to create their own visitor function, users will
have little need to look inside this data structure.  But, for
reference, it is a 3-element list with components:</p>
<dl class="simple">
<dt>f</dt><dd><p>is a frame array, which is used to divide pstack into parts.</p>
</dd>
<dt>lpart</dt><dd><p>points to the base of the topmost part.</p>
</dd>
<dt>pstack</dt><dd><p>is an array of PartComponent objects.</p>
</dd>
</dl>
<p>The <code class="docutils literal notranslate"><span class="pre">state</span></code> output offers a peek into the internal data
structures of the enumeration function.  The client should
treat this as read-only; any modification of the data
structure will cause unpredictable (and almost certainly
incorrect) results.  Also, the components of <code class="docutils literal notranslate"><span class="pre">state</span></code> are
modified in place at each iteration.  Hence, the visitor must
be called at each loop iteration.  Accumulating the <code class="docutils literal notranslate"><span class="pre">state</span></code>
instances and processing them later will not work.</p>
</div></blockquote>
</dd>
</dl>
<p class="rubric">Examples</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.utilities.enumerative</span> <span class="kn">import</span> <span class="n">list_visitor</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.utilities.enumerative</span> <span class="kn">import</span> <span class="n">multiset_partitions_taocp</span>
<span class="gp">&gt;&gt;&gt; </span><span class="c1"># variables components and multiplicities represent the multiset &#39;abb&#39;</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">components</span> <span class="o">=</span> <span class="s1">&#39;ab&#39;</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">multiplicities</span> <span class="o">=</span> <span class="p">[</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">states</span> <span class="o">=</span> <span class="n">multiset_partitions_taocp</span><span class="p">(</span><span class="n">multiplicities</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="nb">list</span><span class="p">(</span><span class="n">list_visitor</span><span class="p">(</span><span class="n">state</span><span class="p">,</span> <span class="n">components</span><span class="p">)</span> <span class="k">for</span> <span class="n">state</span> <span class="ow">in</span> <span class="n">states</span><span class="p">)</span>
<span class="go">[[[&#39;a&#39;, &#39;b&#39;, &#39;b&#39;]],</span>
<span class="go">[[&#39;a&#39;, &#39;b&#39;], [&#39;b&#39;]],</span>
<span class="go">[[&#39;a&#39;], [&#39;b&#39;, &#39;b&#39;]],</span>
<span class="go">[[&#39;a&#39;], [&#39;b&#39;], [&#39;b&#39;]]]</span>
</pre></div>
</div>
<div class="admonition seealso">
<p class="admonition-title">See also</p>
<dl class="simple">
<dt><a class="reference internal" href="iterables.html#sympy.utilities.iterables.multiset_partitions" title="sympy.utilities.iterables.multiset_partitions"><code class="xref py py-obj docutils literal notranslate"><span class="pre">sympy.utilities.iterables.multiset_partitions</span></code></a></dt><dd><p>Takes a multiset as input and directly yields multiset partitions.  It dispatches to a number of functions, including this one, for implementation.  Most users will find it more convenient to use than multiset_partitions_taocp.</p>
</dd>
</dl>
</div>
</dd></dl>

<dl class="py function">
<dt class="sig sig-object py" id="sympy.utilities.enumerative.factoring_visitor">
<span class="sig-prename descclassname"><span class="pre">sympy.utilities.enumerative.</span></span><span class="sig-name descname"><span class="pre">factoring_visitor</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">state</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">primes</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/utilities/enumerative.py#L304-L338"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.utilities.enumerative.factoring_visitor" title="Permalink to this definition">¶</a></dt>
<dd><p>Use with multiset_partitions_taocp to enumerate the ways a
number can be expressed as a product of factors.  For this usage,
the exponents of the prime factors of a number are arguments to
the partition enumerator, while the corresponding prime factors
are input here.</p>
<p class="rubric">Examples</p>
<p>To enumerate the factorings of a number we can think of the elements of the
partition as being the prime factors and the multiplicities as being their
exponents.</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.utilities.enumerative</span> <span class="kn">import</span> <span class="n">factoring_visitor</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.utilities.enumerative</span> <span class="kn">import</span> <span class="n">multiset_partitions_taocp</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy</span> <span class="kn">import</span> <span class="n">factorint</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">primes</span><span class="p">,</span> <span class="n">multiplicities</span> <span class="o">=</span> <span class="nb">zip</span><span class="p">(</span><span class="o">*</span><span class="n">factorint</span><span class="p">(</span><span class="mi">24</span><span class="p">)</span><span class="o">.</span><span class="n">items</span><span class="p">())</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">primes</span>
<span class="go">(2, 3)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">multiplicities</span>
<span class="go">(3, 1)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">states</span> <span class="o">=</span> <span class="n">multiset_partitions_taocp</span><span class="p">(</span><span class="n">multiplicities</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="nb">list</span><span class="p">(</span><span class="n">factoring_visitor</span><span class="p">(</span><span class="n">state</span><span class="p">,</span> <span class="n">primes</span><span class="p">)</span> <span class="k">for</span> <span class="n">state</span> <span class="ow">in</span> <span class="n">states</span><span class="p">)</span>
<span class="go">[[24], [8, 3], [12, 2], [4, 6], [4, 2, 3], [6, 2, 2], [2, 2, 2, 3]]</span>
</pre></div>
</div>
</dd></dl>

<dl class="py function">
<dt class="sig sig-object py" id="sympy.utilities.enumerative.list_visitor">
<span class="sig-prename descclassname"><span class="pre">sympy.utilities.enumerative.</span></span><span class="sig-name descname"><span class="pre">list_visitor</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">state</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">components</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/utilities/enumerative.py#L341-L367"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.utilities.enumerative.list_visitor" title="Permalink to this definition">¶</a></dt>
<dd><p>Return a list of lists to represent the partition.</p>
<p class="rubric">Examples</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.utilities.enumerative</span> <span class="kn">import</span> <span class="n">list_visitor</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.utilities.enumerative</span> <span class="kn">import</span> <span class="n">multiset_partitions_taocp</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">states</span> <span class="o">=</span> <span class="n">multiset_partitions_taocp</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">1</span><span class="p">])</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">s</span> <span class="o">=</span> <span class="nb">next</span><span class="p">(</span><span class="n">states</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">list_visitor</span><span class="p">(</span><span class="n">s</span><span class="p">,</span> <span class="s1">&#39;abc&#39;</span><span class="p">)</span>  <span class="c1"># for multiset &#39;a b b c&#39;</span>
<span class="go">[[&#39;a&#39;, &#39;b&#39;, &#39;b&#39;, &#39;c&#39;]]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">s</span> <span class="o">=</span> <span class="nb">next</span><span class="p">(</span><span class="n">states</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">list_visitor</span><span class="p">(</span><span class="n">s</span><span class="p">,</span> <span class="p">[</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">])</span>  <span class="c1"># for multiset &#39;1 2 2 3</span>
<span class="go">[[1, 2, 2], [3]]</span>
</pre></div>
</div>
</dd></dl>

<p>The approach of the function <code class="docutils literal notranslate"><span class="pre">multiset_partitions_taocp</span></code> is extended
and generalized by the class <code class="docutils literal notranslate"><span class="pre">MultisetPartitionTraverser</span></code>.</p>
<dl class="py class">
<dt class="sig sig-object py" id="sympy.utilities.enumerative.MultisetPartitionTraverser">
<em class="property"><span class="pre">class</span> </em><span class="sig-prename descclassname"><span class="pre">sympy.utilities.enumerative.</span></span><span class="sig-name descname"><span class="pre">MultisetPartitionTraverser</span></span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/utilities/enumerative.py#L370-L1129"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.utilities.enumerative.MultisetPartitionTraverser" title="Permalink to this definition">¶</a></dt>
<dd><p>Has methods to <code class="docutils literal notranslate"><span class="pre">enumerate</span></code> and <code class="docutils literal notranslate"><span class="pre">count</span></code> the partitions of a multiset.</p>
<p>This implements a refactored and extended version of Knuth’s algorithm
7.1.2.5M <a class="reference internal" href="#aocp" id="id1"><span>[AOCP]</span></a>.”</p>
<p>The enumeration methods of this class are generators and return
data structures which can be interpreted by the same visitor
functions used for the output of <code class="docutils literal notranslate"><span class="pre">multiset_partitions_taocp</span></code>.</p>
<p class="rubric">Examples</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.utilities.enumerative</span> <span class="kn">import</span> <span class="n">MultisetPartitionTraverser</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">m</span> <span class="o">=</span> <span class="n">MultisetPartitionTraverser</span><span class="p">()</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">m</span><span class="o">.</span><span class="n">count_partitions</span><span class="p">([</span><span class="mi">4</span><span class="p">,</span><span class="mi">4</span><span class="p">,</span><span class="mi">4</span><span class="p">,</span><span class="mi">2</span><span class="p">])</span>
<span class="go">127750</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">m</span><span class="o">.</span><span class="n">count_partitions</span><span class="p">([</span><span class="mi">3</span><span class="p">,</span><span class="mi">3</span><span class="p">,</span><span class="mi">3</span><span class="p">])</span>
<span class="go">686</span>
</pre></div>
</div>
<div class="admonition seealso">
<p class="admonition-title">See also</p>
<p><a class="reference internal" href="#sympy.utilities.enumerative.multiset_partitions_taocp" title="sympy.utilities.enumerative.multiset_partitions_taocp"><code class="xref py py-obj docutils literal notranslate"><span class="pre">multiset_partitions_taocp</span></code></a>, <a class="reference internal" href="iterables.html#sympy.utilities.iterables.multiset_partitions" title="sympy.utilities.iterables.multiset_partitions"><code class="xref py py-obj docutils literal notranslate"><span class="pre">sympy.utilities.iterables.multiset_partitions</span></code></a></p>
</div>
<p class="rubric">References</p>
<dl class="citation">
<dt class="label" id="aocp"><span class="brackets">AOCP</span><span class="fn-backref">(<a href="#id1">1</a>,<a href="#id2">2</a>,<a href="#id5">3</a>,<a href="#id6">4</a>)</span></dt>
<dd><p>Algorithm 7.1.2.5M in Volume 4A, Combinatoral Algorithms,
Part 1, of The Art of Computer Programming, by Donald Knuth.</p>
</dd>
<dt class="label" id="factorisatio"><span class="brackets"><a class="fn-backref" href="#id3">Factorisatio</a></span></dt>
<dd><p>On a Problem of Oppenheim concerning
“Factorisatio Numerorum” E. R. Canfield, Paul Erdos, Carl
Pomerance, JOURNAL OF NUMBER THEORY, Vol. 17, No. 1. August
1983.  See section 7 for a description of an algorithm
similar to Knuth’s.</p>
</dd>
<dt class="label" id="yorgey"><span class="brackets"><a class="fn-backref" href="#id4">Yorgey</a></span></dt>
<dd><p>Generating Multiset Partitions, Brent Yorgey, The
Monad.Reader, Issue 8, September 2007.</p>
</dd>
</dl>
<dl class="py method">
<dt class="sig sig-object py" id="sympy.utilities.enumerative.MultisetPartitionTraverser.count_partitions">
<span class="sig-name descname"><span class="pre">count_partitions</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">multiplicities</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/utilities/enumerative.py#L1007-L1129"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.utilities.enumerative.MultisetPartitionTraverser.count_partitions" title="Permalink to this definition">¶</a></dt>
<dd><p>Returns the number of partitions of a multiset whose components
have the multiplicities given in <code class="docutils literal notranslate"><span class="pre">multiplicities</span></code>.</p>
<p>For larger counts, this method is much faster than calling one
of the enumerators and counting the result.  Uses dynamic
programming to cut down on the number of nodes actually
explored.  The dictionary used in order to accelerate the
counting process is stored in the <code class="docutils literal notranslate"><span class="pre">MultisetPartitionTraverser</span></code>
object and persists across calls.  If the user does not
expect to call <code class="docutils literal notranslate"><span class="pre">count_partitions</span></code> for any additional
multisets, the object should be cleared to save memory.  On
the other hand, the cache built up from one count run can
significantly speed up subsequent calls to <code class="docutils literal notranslate"><span class="pre">count_partitions</span></code>,
so it may be advantageous not to clear the object.</p>
<p class="rubric">Examples</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.utilities.enumerative</span> <span class="kn">import</span> <span class="n">MultisetPartitionTraverser</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">m</span> <span class="o">=</span> <span class="n">MultisetPartitionTraverser</span><span class="p">()</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">m</span><span class="o">.</span><span class="n">count_partitions</span><span class="p">([</span><span class="mi">9</span><span class="p">,</span><span class="mi">8</span><span class="p">,</span><span class="mi">2</span><span class="p">])</span>
<span class="go">288716</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">m</span><span class="o">.</span><span class="n">count_partitions</span><span class="p">([</span><span class="mi">2</span><span class="p">,</span><span class="mi">2</span><span class="p">])</span>
<span class="go">9</span>
<span class="gp">&gt;&gt;&gt; </span><span class="k">del</span> <span class="n">m</span>
</pre></div>
</div>
<p class="rubric">Notes</p>
<p>If one looks at the workings of Knuth’s algorithm M <a class="reference internal" href="#aocp" id="id5"><span>[AOCP]</span></a>, it
can be viewed as a traversal of a binary tree of parts.  A
part has (up to) two children, the left child resulting from
the spread operation, and the right child from the decrement
operation.  The ordinary enumeration of multiset partitions is
an in-order traversal of this tree, and with the partitions
corresponding to paths from the root to the leaves. The
mapping from paths to partitions is a little complicated,
since the partition would contain only those parts which are
leaves or the parents of a spread link, not those which are
parents of a decrement link.</p>
<p>For counting purposes, it is sufficient to count leaves, and
this can be done with a recursive in-order traversal.  The
number of leaves of a subtree rooted at a particular part is a
function only of that part itself, so memoizing has the
potential to speed up the counting dramatically.</p>
<p>This method follows a computational approach which is similar
to the hypothetical memoized recursive function, but with two
differences:</p>
<ol class="arabic simple">
<li><p>This method is iterative, borrowing its structure from the
other enumerations and maintaining an explicit stack of
parts which are in the process of being counted.  (There
may be multisets which can be counted reasonably quickly by
this implementation, but which would overflow the default
Python recursion limit with a recursive implementation.)</p></li>
<li><p>Instead of using the part data structure directly, a more
compact key is constructed.  This saves space, but more
importantly coalesces some parts which would remain
separate with physical keys.</p></li>
</ol>
<p>Unlike the enumeration functions, there is currently no _range
version of count_partitions.  If someone wants to stretch
their brain, it should be possible to construct one by
memoizing with a histogram of counts rather than a single
count, and combining the histograms.</p>
</dd></dl>

<dl class="py method">
<dt class="sig sig-object py" id="sympy.utilities.enumerative.MultisetPartitionTraverser.enum_all">
<span class="sig-name descname"><span class="pre">enum_all</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">multiplicities</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/utilities/enumerative.py#L736-L781"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.utilities.enumerative.MultisetPartitionTraverser.enum_all" title="Permalink to this definition">¶</a></dt>
<dd><p>Enumerate the partitions of a multiset.</p>
<p class="rubric">Examples</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.utilities.enumerative</span> <span class="kn">import</span> <span class="n">list_visitor</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.utilities.enumerative</span> <span class="kn">import</span> <span class="n">MultisetPartitionTraverser</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">m</span> <span class="o">=</span> <span class="n">MultisetPartitionTraverser</span><span class="p">()</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">states</span> <span class="o">=</span> <span class="n">m</span><span class="o">.</span><span class="n">enum_all</span><span class="p">([</span><span class="mi">2</span><span class="p">,</span><span class="mi">2</span><span class="p">])</span>
<span class="gp">&gt;&gt;&gt; </span><span class="nb">list</span><span class="p">(</span><span class="n">list_visitor</span><span class="p">(</span><span class="n">state</span><span class="p">,</span> <span class="s1">&#39;ab&#39;</span><span class="p">)</span> <span class="k">for</span> <span class="n">state</span> <span class="ow">in</span> <span class="n">states</span><span class="p">)</span>
<span class="go">[[[&#39;a&#39;, &#39;a&#39;, &#39;b&#39;, &#39;b&#39;]],</span>
<span class="go">[[&#39;a&#39;, &#39;a&#39;, &#39;b&#39;], [&#39;b&#39;]],</span>
<span class="go">[[&#39;a&#39;, &#39;a&#39;], [&#39;b&#39;, &#39;b&#39;]],</span>
<span class="go">[[&#39;a&#39;, &#39;a&#39;], [&#39;b&#39;], [&#39;b&#39;]],</span>
<span class="go">[[&#39;a&#39;, &#39;b&#39;, &#39;b&#39;], [&#39;a&#39;]],</span>
<span class="go">[[&#39;a&#39;, &#39;b&#39;], [&#39;a&#39;, &#39;b&#39;]],</span>
<span class="go">[[&#39;a&#39;, &#39;b&#39;], [&#39;a&#39;], [&#39;b&#39;]],</span>
<span class="go">[[&#39;a&#39;], [&#39;a&#39;], [&#39;b&#39;, &#39;b&#39;]],</span>
<span class="go">[[&#39;a&#39;], [&#39;a&#39;], [&#39;b&#39;], [&#39;b&#39;]]]</span>
</pre></div>
</div>
<div class="admonition seealso">
<p class="admonition-title">See also</p>
<dl class="simple">
<dt><a class="reference internal" href="#sympy.utilities.enumerative.multiset_partitions_taocp" title="sympy.utilities.enumerative.multiset_partitions_taocp"><code class="xref py py-obj docutils literal notranslate"><span class="pre">multiset_partitions_taocp</span></code></a></dt><dd><p>which provides the same result as this method, but is about twice as fast.  Hence, enum_all is primarily useful for testing.  Also see the function for a discussion of states and visitors.</p>
</dd>
</dl>
</div>
</dd></dl>

<dl class="py method">
<dt class="sig sig-object py" id="sympy.utilities.enumerative.MultisetPartitionTraverser.enum_large">
<span class="sig-name descname"><span class="pre">enum_large</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">multiplicities</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">lb</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/utilities/enumerative.py#L853-L912"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.utilities.enumerative.MultisetPartitionTraverser.enum_large" title="Permalink to this definition">¶</a></dt>
<dd><p>Enumerate the partitions of a multiset with lb &lt; num(parts)</p>
<p>Equivalent to enum_range(multiplicities, lb, sum(multiplicities))</p>
<dl class="field-list">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><p><strong>multiplicities</strong></p>
<blockquote>
<div><p>list of multiplicities of the components of the multiset.</p>
</div></blockquote>
<p><strong>lb</strong></p>
<blockquote>
<div><p>Number of parts in the partition must be greater than
this lower bound.</p>
</div></blockquote>
</dd>
</dl>
<p class="rubric">Examples</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.utilities.enumerative</span> <span class="kn">import</span> <span class="n">list_visitor</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.utilities.enumerative</span> <span class="kn">import</span> <span class="n">MultisetPartitionTraverser</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">m</span> <span class="o">=</span> <span class="n">MultisetPartitionTraverser</span><span class="p">()</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">states</span> <span class="o">=</span> <span class="n">m</span><span class="o">.</span><span class="n">enum_large</span><span class="p">([</span><span class="mi">2</span><span class="p">,</span><span class="mi">2</span><span class="p">],</span> <span class="mi">2</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="nb">list</span><span class="p">(</span><span class="n">list_visitor</span><span class="p">(</span><span class="n">state</span><span class="p">,</span> <span class="s1">&#39;ab&#39;</span><span class="p">)</span> <span class="k">for</span> <span class="n">state</span> <span class="ow">in</span> <span class="n">states</span><span class="p">)</span>
<span class="go">[[[&#39;a&#39;, &#39;a&#39;], [&#39;b&#39;], [&#39;b&#39;]],</span>
<span class="go">[[&#39;a&#39;, &#39;b&#39;], [&#39;a&#39;], [&#39;b&#39;]],</span>
<span class="go">[[&#39;a&#39;], [&#39;a&#39;], [&#39;b&#39;, &#39;b&#39;]],</span>
<span class="go">[[&#39;a&#39;], [&#39;a&#39;], [&#39;b&#39;], [&#39;b&#39;]]]</span>
</pre></div>
</div>
<div class="admonition seealso">
<p class="admonition-title">See also</p>
<p><a class="reference internal" href="#sympy.utilities.enumerative.MultisetPartitionTraverser.enum_all" title="sympy.utilities.enumerative.MultisetPartitionTraverser.enum_all"><code class="xref py py-obj docutils literal notranslate"><span class="pre">enum_all</span></code></a>, <a class="reference internal" href="#sympy.utilities.enumerative.MultisetPartitionTraverser.enum_small" title="sympy.utilities.enumerative.MultisetPartitionTraverser.enum_small"><code class="xref py py-obj docutils literal notranslate"><span class="pre">enum_small</span></code></a>, <a class="reference internal" href="#sympy.utilities.enumerative.MultisetPartitionTraverser.enum_range" title="sympy.utilities.enumerative.MultisetPartitionTraverser.enum_range"><code class="xref py py-obj docutils literal notranslate"><span class="pre">enum_range</span></code></a></p>
</div>
</dd></dl>

<dl class="py method">
<dt class="sig sig-object py" id="sympy.utilities.enumerative.MultisetPartitionTraverser.enum_range">
<span class="sig-name descname"><span class="pre">enum_range</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">multiplicities</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">lb</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">ub</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/utilities/enumerative.py#L914-L974"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.utilities.enumerative.MultisetPartitionTraverser.enum_range" title="Permalink to this definition">¶</a></dt>
<dd><p>Enumerate the partitions of a multiset with
<code class="docutils literal notranslate"><span class="pre">lb</span> <span class="pre">&lt;</span> <span class="pre">num(parts)</span> <span class="pre">&lt;=</span> <span class="pre">ub</span></code>.</p>
<p>In particular, if partitions with exactly <code class="docutils literal notranslate"><span class="pre">k</span></code> parts are
desired, call with <code class="docutils literal notranslate"><span class="pre">(multiplicities,</span> <span class="pre">k</span> <span class="pre">-</span> <span class="pre">1,</span> <span class="pre">k)</span></code>.  This
method generalizes enum_all, enum_small, and enum_large.</p>
<p class="rubric">Examples</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.utilities.enumerative</span> <span class="kn">import</span> <span class="n">list_visitor</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.utilities.enumerative</span> <span class="kn">import</span> <span class="n">MultisetPartitionTraverser</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">m</span> <span class="o">=</span> <span class="n">MultisetPartitionTraverser</span><span class="p">()</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">states</span> <span class="o">=</span> <span class="n">m</span><span class="o">.</span><span class="n">enum_range</span><span class="p">([</span><span class="mi">2</span><span class="p">,</span><span class="mi">2</span><span class="p">],</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="nb">list</span><span class="p">(</span><span class="n">list_visitor</span><span class="p">(</span><span class="n">state</span><span class="p">,</span> <span class="s1">&#39;ab&#39;</span><span class="p">)</span> <span class="k">for</span> <span class="n">state</span> <span class="ow">in</span> <span class="n">states</span><span class="p">)</span>
<span class="go">[[[&#39;a&#39;, &#39;a&#39;, &#39;b&#39;], [&#39;b&#39;]],</span>
<span class="go">[[&#39;a&#39;, &#39;a&#39;], [&#39;b&#39;, &#39;b&#39;]],</span>
<span class="go">[[&#39;a&#39;, &#39;b&#39;, &#39;b&#39;], [&#39;a&#39;]],</span>
<span class="go">[[&#39;a&#39;, &#39;b&#39;], [&#39;a&#39;, &#39;b&#39;]]]</span>
</pre></div>
</div>
</dd></dl>

<dl class="py method">
<dt class="sig sig-object py" id="sympy.utilities.enumerative.MultisetPartitionTraverser.enum_small">
<span class="sig-name descname"><span class="pre">enum_small</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">multiplicities</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">ub</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/utilities/enumerative.py#L783-L851"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.utilities.enumerative.MultisetPartitionTraverser.enum_small" title="Permalink to this definition">¶</a></dt>
<dd><p>Enumerate multiset partitions with no more than <code class="docutils literal notranslate"><span class="pre">ub</span></code> parts.</p>
<p>Equivalent to enum_range(multiplicities, 0, ub)</p>
<dl class="field-list">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><p><strong>multiplicities</strong></p>
<blockquote>
<div><p>list of multiplicities of the components of the multiset.</p>
</div></blockquote>
<p><strong>ub</strong></p>
<blockquote>
<div><p>Maximum number of parts</p>
</div></blockquote>
</dd>
</dl>
<p class="rubric">Examples</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.utilities.enumerative</span> <span class="kn">import</span> <span class="n">list_visitor</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.utilities.enumerative</span> <span class="kn">import</span> <span class="n">MultisetPartitionTraverser</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">m</span> <span class="o">=</span> <span class="n">MultisetPartitionTraverser</span><span class="p">()</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">states</span> <span class="o">=</span> <span class="n">m</span><span class="o">.</span><span class="n">enum_small</span><span class="p">([</span><span class="mi">2</span><span class="p">,</span><span class="mi">2</span><span class="p">],</span> <span class="mi">2</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="nb">list</span><span class="p">(</span><span class="n">list_visitor</span><span class="p">(</span><span class="n">state</span><span class="p">,</span> <span class="s1">&#39;ab&#39;</span><span class="p">)</span> <span class="k">for</span> <span class="n">state</span> <span class="ow">in</span> <span class="n">states</span><span class="p">)</span>
<span class="go">[[[&#39;a&#39;, &#39;a&#39;, &#39;b&#39;, &#39;b&#39;]],</span>
<span class="go">[[&#39;a&#39;, &#39;a&#39;, &#39;b&#39;], [&#39;b&#39;]],</span>
<span class="go">[[&#39;a&#39;, &#39;a&#39;], [&#39;b&#39;, &#39;b&#39;]],</span>
<span class="go">[[&#39;a&#39;, &#39;b&#39;, &#39;b&#39;], [&#39;a&#39;]],</span>
<span class="go">[[&#39;a&#39;, &#39;b&#39;], [&#39;a&#39;, &#39;b&#39;]]]</span>
</pre></div>
</div>
<p>The implementation is based, in part, on the answer given to
exercise 69, in Knuth <a class="reference internal" href="#aocp" id="id6"><span>[AOCP]</span></a>.</p>
<div class="admonition seealso">
<p class="admonition-title">See also</p>
<p><a class="reference internal" href="#sympy.utilities.enumerative.MultisetPartitionTraverser.enum_all" title="sympy.utilities.enumerative.MultisetPartitionTraverser.enum_all"><code class="xref py py-obj docutils literal notranslate"><span class="pre">enum_all</span></code></a>, <a class="reference internal" href="#sympy.utilities.enumerative.MultisetPartitionTraverser.enum_large" title="sympy.utilities.enumerative.MultisetPartitionTraverser.enum_large"><code class="xref py py-obj docutils literal notranslate"><span class="pre">enum_large</span></code></a>, <a class="reference internal" href="#sympy.utilities.enumerative.MultisetPartitionTraverser.enum_range" title="sympy.utilities.enumerative.MultisetPartitionTraverser.enum_range"><code class="xref py py-obj docutils literal notranslate"><span class="pre">enum_range</span></code></a></p>
</div>
</dd></dl>

</dd></dl>

</section>


            <div class="clearer"></div>
          </div>
        </div>
      </div>
      <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
        <div class="sphinxsidebarwrapper">
            <p class="logo"><a href="../../index.html">
              <img class="logo" src="../../_static/sympylogo.png" alt="Logo"/>
            </a></p>
  <h4>Previous topic</h4>
  <p class="topless"><a href="decorator.html"
                        title="previous chapter">Decorator</a></p>
  <h4>Next topic</h4>
  <p class="topless"><a href="iterables.html"
                        title="next chapter">Iterables</a></p>
  <div role="note" aria-label="source link">
    <h3>This Page</h3>
    <ul class="this-page-menu">
      <li><a href="../../_sources/modules/utilities/enumerative.rst.txt"
            rel="nofollow">Show Source</a></li>
    </ul>
   </div>
<div id="searchbox" style="display: none" role="search">
  <h3 id="searchlabel">Quick search</h3>
    <div class="searchformwrapper">
    <form class="search" action="https://docs.sympy.org/latest/search.html" method="get">
      <input type="text" name="q" aria-labelledby="searchlabel" autocomplete="off" autocorrect="off" autocapitalize="off" spellcheck="false"/>
      <input type="submit" value="Go" />
    </form>
    </div>
</div>
<script>$('#searchbox').show(0);</script>
        </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../../genindex.html" title="General Index"
             >index</a></li>
        <li class="right" >
          <a href="../../py-modindex.html" title="Python Module Index"
             >modules</a> |</li>
        <li class="right" >
          <a href="iterables.html" title="Iterables"
             >next</a> |</li>
        <li class="right" >
          <a href="decorator.html" title="Decorator"
             >previous</a> |</li>
        <li class="nav-item nav-item-0"><a href="../../index.html">SymPy 1.9 documentation</a> &#187;</li>
          <li class="nav-item nav-item-1"><a href="../index.html" >SymPy Modules Reference</a> &#187;</li>
          <li class="nav-item nav-item-2"><a href="index.html" >Utilities</a> &#187;</li>
        <li class="nav-item nav-item-this"><a href="#">Enumerative</a></li> 
      </ul>
    </div>
    <div class="footer" role="contentinfo">
        &#169; Copyright 2021 SymPy Development Team.
      Last updated on Sep 30, 2021.
      Created using <a href="https://www.sphinx-doc.org/">Sphinx</a> 4.1.2.
    </div>
  </body>

<!-- Mirrored from docs.sympy.org/latest/modules/utilities/enumerative.html by HTTrack Website Copier/3.x [XR&CO'2014], Sat, 15 Jan 2022 03:28:12 GMT -->
</html>